import java.util.Arrays;
import java.util.Random;

/**
 * provide the a number of sorting methods that operate on an array
 * @author BaoTam_Vo
 *
 * @param <T>
 */
public class Sort<T extends Comparable<T>> implements SortInterface<T> {
	Comparator comparator = new Comparator();
	int swapcount = 0;
	
	/**
	 * Perform insertion sort on the given array
	 * @param array
	 */
	public void insertionSort(T[] array) {
		comparator.reset();
		for(int iMain = 0; iMain <= array.length-1; iMain++) {
			T 	toInsert  = array[iMain];
			int iPrevArray = iMain-1;
			while(iPrevArray >= 0) {
				if(comparator.compare(toInsert,array[iPrevArray]) < 0) {
					array[iPrevArray+1] = array[iPrevArray];
				}
				else {
					break;
				}
				iPrevArray--;
			}
			array[iPrevArray+1] = toInsert;
		}
		System.out.println("n : " + array.length + "--insertion compare count : " + comparator.getCompareCount());
	}
	
	/**
	 * Perform selection sort on the given array
	 * @param array
	 */
	public void selectionSort(T[] array) {
		comparator.reset();
		for(int iMain = 0; iMain <= array.length-2; iMain++) {
			T 	minInTempList 		= array[iMain];
			int minInTempListIndex	= iMain;
			for(int iTemp = iMain; iTemp <= array.length-1; iTemp++) {
				if(comparator.compare(array[iTemp],minInTempList) < 0) {
					minInTempList 	   = array[iTemp];
					minInTempListIndex = iTemp;
				}
			}
			array[minInTempListIndex] = array[iMain];
			array[iMain] = minInTempList;
		}
		System.out.println("n : " + array.length + "--selection compare count : " + comparator.getCompareCount());
	}

	
	/**
	 * Perform merge sort on the given array
	 * @param array
	 */
	public void mergeSort(T[] array) {
		System.out.println("<<merge sort>>");
		comparator.reset();
		T[] result = mergeSortRecursive(array);
		for(int i = 0; i <= array.length-1; i++) {
			array[i] = result[i];
		}
		System.out.println("n : " + array.length + "--merge compare count : " + comparator.getCompareCount());
	}
	
	/**
	 * recursive method helper for merge sort
	 * @param array
	 */
	private T[] mergeSortRecursive(T[] array) {
		System.out.println("begin merge sort: " + Arrays.toString(array));
		if(array.length <= 1) {
			System.out.println("length <= 1 : return");
			return array;
		}
		
		int midIndex = array.length/2;
		System.out.println("left: " + Arrays.toString(Arrays.copyOfRange(array, 0, midIndex)));
		System.out.println("right: " + Arrays.toString(Arrays.copyOfRange(array,midIndex, array.length)));
		T[] leftArray  = mergeSortRecursive(Arrays.copyOfRange(array, 0, midIndex));
		T[] rightArray = mergeSortRecursive(Arrays.copyOfRange(array,midIndex, array.length));
		
		return merge(leftArray, rightArray);
	}
	
	/**
	 * merge two arrays together. The elements in the result are in order
	 * @param leftArray
	 * @param rightArray
	 */
	private T[] merge(T[] leftArray, T[] rightArray) {
		System.out.println("begin merge");
		System.out.println("--l: " + Arrays.toString(leftArray));
		System.out.println("--r: " + Arrays.toString(rightArray));
		@SuppressWarnings("unchecked")
		T[] result = (T[]) new Comparable[leftArray.length + rightArray.length];
		int iResult = 0;
		int iLeft = 0;
		int iRight = 0;
		System.out.println("move left and right to result");
		while((iLeft <= leftArray.length-1) && (iRight <= rightArray.length-1)) {
			if (comparator.compare(leftArray[iLeft],rightArray[iRight]) <= 0) {
				System.out.println("---" + leftArray[iLeft] + " <= " + rightArray[iRight]);
				result[iResult] = leftArray[iLeft];
				iLeft++;
				iResult++;
			}
			else {
				System.out.println("---" + leftArray[iLeft] + " > " + rightArray[iRight]);
				result[iResult] = rightArray[iRight];
				iRight++;
				iResult++;
			}
		}
		
		System.out.println("---ileft: " + iLeft);
		System.out.println("---irigh: " + iRight);
		
		System.out.println("move remain left to result");
		while(iLeft <= leftArray.length-1) {
			result[iResult] = leftArray[iLeft];
			iLeft++;
			iResult++;
		}
		
		System.out.println("move remain right to result");
		while(iRight <= rightArray.length-1) {
			result[iResult] = rightArray[iRight];
			iRight++;
			iResult++;
		}
		
		System.out.println("--result: " + Arrays.toString(result));
		return result;
	}
	
	/**
	 * Perform quick sort on the given array
	 * @param array
	 */
	@Override
	public void quickSort(T[] array) {
		swapcount = 0;
		comparator.reset();
		System.out.println("<<quick sort>>");
		quickSortRecursive(array,0,array.length-1);
		System.out.println("n : " + array.length + "--quick compare count : " + comparator.getCompareCount() + "--swap count: " + swapcount);
	}
	
	/**
	 * Recursive helper for quick sort
	 * @param array
	 * @param iStart, starting index
	 * @param iEnd, ending index
	 */
	private void quickSortRecursive(T[] array, int iStart, int iEnd) {
		System.out.println("begin quick sort");
		
		if (iStart >= iEnd) {
			System.out.println("start >= end : return");
			return;
		}
		System.out.println("origin: " + Arrays.toString(array));
		System.out.println(Arrays.toString(Arrays.copyOfRange(array, iStart, iEnd+1)));
		int iPivot = (iStart+iEnd)/2;
		T pivot = array[iPivot];
		System.out.println("--pv: " + pivot);
		/*
		for(int iMain = iStart+1; iMain <= iEnd; iMain++) {
			if(comparer.compare(array[iMain], pivot) < 0) {
				T movedElem = array[iMain];
				for(int iTemp = iMain-1; iTemp >= iPivot; iTemp--) {
					array[iTemp+1] = array[iTemp];
				}
				array[iPivot] = movedElem;
				iPivot++;
				System.out.println("--partition: " + Arrays.toString(Arrays.copyOfRange(array, iStart, iEnd+1)));
			}
		}*/
		
		int iLeft  = iPivot-1;
		int iRight = iPivot+1;
		while(iLeft >= iStart || iRight <= iEnd) {
			//check left partition
			if(iLeft >= iStart) {
				if(comparator.compare(array[iLeft], pivot) > 0) {
					T movedElem = array[iLeft];
					for(int iTemp = iLeft+1; iTemp <= iPivot; iTemp++) {
						array[iTemp-1] = array[iTemp];
						swapcount++;
					}
					array[iPivot] = movedElem;
					iPivot--;
				}
				iLeft--;
			}
			
			//check right partition
			if(iRight <= iEnd) {
				if(comparator.compare(array[iRight], pivot) < 0) {
					T movedElem = array[iRight];
					for(int iTemp = iRight-1; iTemp >= iPivot; iTemp--) {
						array[iTemp+1] = array[iTemp];
						swapcount++;
					}
					array[iPivot] = movedElem;
					iPivot++;
				}
				iRight++;
			}
		}
		System.out.println("--after partition: " + Arrays.toString(Arrays.copyOfRange(array, iStart, iEnd+1)));
		//debug ---
		if(iPivot > iStart) {
			System.out.println("--l: " + Arrays.toString(Arrays.copyOfRange(array, iStart, iPivot)));
		}
		if(iEnd+1 > iPivot+1) {
			System.out.println("--r: " + Arrays.toString(Arrays.copyOfRange(array, iPivot+1, iEnd+1)));
		}
		//-----
		quickSortRecursive(array,iStart, iPivot-1);
		quickSortRecursive(array,iPivot+1, iEnd);
		
	}
	
	/**
	 * main method used for debugging
	 * @param args
	 */
	public static void main(String[] args) {
		Sort<Integer> sort = new Sort<Integer>();
		//Random randGen = new Random(System.nanoTime());
		//int length = 2;
		/*
		Integer[] intArr = new Integer[length];
		for(int i = 0; i <= length-1; i++) {
			intArr[i] = (randGen.nextInt(length));
		}*/
		
		Integer[] intArr= {1,1,0,0,3,4,1,4,5,1,1,1,1};
		System.out.println("orig: " + Arrays.toString(intArr));
		sort.quickSort((Integer[])intArr);
		
		System.out.println(Arrays.toString(intArr));
	}
	
	/**
	 * provide the counter for the number of comparison
	 * @author BaoTam_Vo
	 *
	 */
	private class Comparator {
		private int compareCount = 0;
		
		/**
		 * set the counter to 0
		 */
		public void reset() {
			compareCount = 0;
		}
		
		/**
		 * @return number of comparisons
		 */
		public int getCompareCount() {
			return compareCount;
		}
		
		/**
		 * compare to object return a.compareTo(b) and increment the counter
		 * @param a
		 * @param b
		 * @return a.compareTo(b)
		 */
		public int compare(T a, T b) {
			compareCount++;
			return a.compareTo(b);
		}
	}
}
